﻿//
// Created by Freeman on 2022/4/13.
//

#ifndef DATA_STRUCTURE_REVIEW_WEIGHTED_DIRECTED_MAT_GRAPH_HPP
#define DATA_STRUCTURE_REVIEW_WEIGHTED_DIRECTED_MAT_GRAPH_HPP

#include <utility>

#include "WeightedMatGraph.hpp"

class WeightedDirectedMatGraph : public WeightedMatGraph {
private:

    /**
     * 实现共有函数maxFlow(int,int)的核心过程。之所以提供该函数，是为了提供求残差图的方法。
     * @param src
     * @param sink
     * @param residual
     * @return
     */
    int maxFlow(int src, int sink, WeightedDirectedMatGraph &residual) {
        int flow = 0;
        bool existPath;
        std::vector<bool> visit(nVex, false);
        std::vector<int> path = residual.findSimplePath(src, sink, visit, existPath);
        while (existPath) {
            // 求“残差容量”，即路径上各条边中权值的最小值
            int residualCapacity = INT_MAX; // 残差容量
            for (int i = 0; i < path.size() - 1; i++) {
                int u = path[i];
                int v = path[i + 1];
                if (residual.adjMat[u][v] < residualCapacity) residualCapacity = residual.adjMat[u][v];
            }
            flow += residualCapacity;
            // 更新残差图
            for (int i = 0; i < path.size() - 1; i++) {
                int u = path[i];
                int v = path[i + 1];
                residual.subtractWeight(u, v, residualCapacity);
                if (residual.adjMat[v][u] == INT_MAX) { // 不存在反向边时，添加反向边
                    residual.adjMat[v][u] = residualCapacity;
                }
                else { // 存在反向边时，增加反向边的权值
                    residual.addWeight(v, u, residualCapacity);
                }
            }
            // 重新寻找路径
            visit = std::vector<bool>(nVex, false);
            path = residual.findSimplePath(src, sink, visit, existPath);
        }
        return flow;
    }

public:
    explicit WeightedDirectedMatGraph(int nVex) : WeightedMatGraph(nVex) {}

    explicit WeightedDirectedMatGraph(std::vector<std::vector<int>> adjMat) : WeightedMatGraph(std::move(adjMat)) {}

    void addEdge(int tail, int head, int weight) override {
        adjMat[tail][head] = weight;
    }

    /**
     * 删除一条边
     * @param head
     * @param tail
     */
    void deleteEdge(int tail, int head) {
        adjMat[tail][head] = INT_MAX;
    }

    /**
     * 判断是否存在边tail->head
     * @param tail
     * @param head
     * @return 存在边tail->head时，返回true
     */
    bool existEdge(int tail, int head) {
        return adjMat[tail][head] > 0 && adjMat[tail][head] < INT_MAX;
    }

    /**
     * 增加一条边的权值
     * @param tail
     * @param head
     * @param weight
     */
    void addWeight(int tail, int head, int weight) {
        adjMat[tail][head] += weight;
    }

    /**
     * 减少一条边的权值。如果减少权值后边的权值变为0，将删除这条边。
     * @param tail
     * @param head
     * @param weight
     * @return 如果成功地减少了权值，返回true。当weight大于边目前的权值时，返回false。
     */
    bool subtractWeight(int tail, int head, int weight) {
        if (weight > adjMat[tail][head]) return false;
        adjMat[tail][head] -= weight;
        if (adjMat[tail][head] == 0) adjMat[tail][head] = INT_MAX;
        return true;
    }

    /**
     * 判断是否存在src到dst的路径
     * @param src
     * @param dst
     * @return 当存在src到dst的路径时，返回true。
     */
    bool existPath(int src, int dst) {
        bool exist;
        std::vector<bool> visit(nVex, false);
        findSimplePath(src, dst, visit, exist);
        return exist;
    }

    /**
     * 寻找源点到终点的简单路径
     * @param src
     * @param dst
     * @param visit 访问数组
     * @param found 是否存在src到dst的路径
     * @return 简单路径上经过的顶点，第一个和最后一个顶点是源点和终点
     */
    std::vector<int> findSimplePath(int src, int dst, std::vector<bool> &visit, bool &found) {
        std::vector<int> path;
        visit[src] = true;
        for (int v = 0; v < nVex; v++) { // 遍历邻接的未访问顶点
            if (v == src || adjMat[src][v] == INT_MAX || visit[v]) continue;
            if (v == dst) { // 直连
                found = true;
                path = {src, dst};
                return path;
            }
            path = findSimplePath(v, dst, visit, found);
            if (!found) continue;
            else { // 在子任务中找到路径
                path.insert(path.begin(), src);
                return path;
            }
        }
        // 在任何子任务中均无法找到路径，表明不存在src到dst的路径
        visit[src] = false;
        found = false;
        return path;
    }

    /**
     * 求源点到汇点的最大流。实现了Ford–Fulkerson算法。
     * @param src 源点ID
     * @param sink 汇点ID
     * @return 源点到汇点的最大流量
     */
    int maxFlow(int src, int sink) {
        WeightedDirectedMatGraph residual(adjMat);
        return maxFlow(src, sink, residual);
    }

    /**
     * 将顶点分割为集合S和T，并使得该分割为最小分割，即从集合S到T的边的权值之和最小。
     * @param S 包含源点src的集合
     * @param T 包含汇点sink的集合
     * @param src 源点
     * @param sink 汇点
     */
    void minCut(std::set<int> &S, std::set<int> &T, int src, int sink) {
        WeightedDirectedMatGraph residual(adjMat);
        maxFlow(src, sink, residual);
        S.insert(src);
        T.insert(sink);
        for (int v = 0; v < nVex; v++) {
            if (v == src) continue; // 根据existPath的实现，src到自身不存在路径，需要加入此判定避免将src加入T
            if (residual.existPath(src, v)) S.insert(v);
            else T.insert(v);
        }
    }

    /**
     * 生成样例图
     * @return 样例图
     */
    static WeightedDirectedMatGraph generateSampleGraph() {
        WeightedDirectedMatGraph graph(6);
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 10);
        graph.addEdge(1, 2, 2);
        graph.addEdge(1, 3, 4);
        graph.addEdge(1, 4, 8);
        graph.addEdge(2, 4, 9);
        graph.addEdge(4, 3, 6);
        graph.addEdge(3, 5, 10);
        graph.addEdge(4, 5, 10);
        return graph;
    }
};

#endif //DATA_STRUCTURE_REVIEW_WEIGHTED_DIRECTED_MAT_GRAPH_HPP
